package practice;

import cn.mengfly.algorithm.collection.queue.LinkedQueue;
import cn.mengfly.algorithm.collection.queue.Queue;
import cn.mengfly.algorithm.collection.stack.LinkedStack;
import cn.mengfly.algorithm.collection.stack.Stack;
import org.junit.Assert;
import org.junit.Test;

import java.util.Objects;

/**
 * @author wangp
 */
@SuppressWarnings({"unused", "AlibabaLowerCamelCaseVariableNaming", "AlibabaClassNamingShouldBeCamel"})
public class Practice_1_3 {


    @Test
    public void test_1_3_4_Parentheses() {

        String testExpress = "[()]{}{[()()]()}";
        Assert.assertTrue(parentheses(testExpress));

        testExpress = "[(])";
        Assert.assertFalse(parentheses(testExpress));

    }

    private boolean parentheses(String testExpress) {
        Stack<Character> expressStack = new LinkedStack<>();
        for (char c : testExpress.toCharArray()) {
            Character pop;
            switch (c) {
                case ']':
                    pop = expressStack.pop();
                    if (!Objects.equals(pop, '[')) {
                        return false;
                    }
                    break;
                case ')':
                    pop = expressStack.pop();
                    if (!Objects.equals(pop, '(')) {
                        return false;
                    }
                    break;
                case '}':
                    pop = expressStack.pop();
                    if (!Objects.equals(pop, '{')) {
                        return false;
                    }
                    break;
                default:
                    expressStack.push(c);
            }
        }
        return expressStack.isEmpty();
    }

    /**
     * M 个人连续报数，数到 N 的人出局，然后继续报数，直到剩下最后一个人，问：谁能留到最后
     */
    @Test
    public void test_1_3_37_Josephus() {
        int m = 7;
        int n = 2;
        josephus(m, n);
    }

    private void josephus(int m, int n) {
        Queue<Integer> queue = new LinkedQueue<>();
        for (int i = 0; i < m; i++) {
            queue.enqueue(i);
        }
        int i = 1;
        while (!queue.isEmpty()) {
            final Integer dequeue = queue.dequeue();
            if (i == n) {
                System.out.print(dequeue + " ");
                i = 1;
            } else {
                queue.enqueue(dequeue);
                i++;
            }
        }
    }


}
